package work.shuangzhizhen;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author WDH
 * @description
 * @date 2025年01月13日 16:53
 */

public class Problem18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length - 3; i++) {
            //這裏設置long是為了避免溢出，因爲int+long是long，在用例裏有相加后為負數，所以用long
            long x = nums[i];
            if (i > 0 && x == nums[i - 1]) continue;
            if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (x + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) continue;
            for (int j = i + 1; j < nums.length - 2; j++) {
                long y = nums[j];
                if (j > i + 1 && y == nums[j - 1]) continue;
                if (x + y + nums[j + 1] + nums[j + 2] > target) break;
                if (x + y + nums[nums.length - 1] + nums[nums.length - 2] < target) continue;
                int head = j + 1;
                int tail = nums.length - 1;
                while (head < tail) {
                    long sum = x + y + nums[head] + nums[tail];
                    if (sum < target) head++;
                    else if (sum > target) tail--;
                    else {
                        //這裏是爲了符合符合我們ArrayList的要求，裏面要求包含int
                        List list = Arrays.asList((int) x, (int) y, nums[head], nums[tail]);
                        quadruplets.add(list);

                        //爲什麽這個不行呢，比如2222  target8 當他跳出循環的時候 head == tail都指向了最後一個2，然後再進行head++就空指針了
                        //三数的答案
                        while (nums[head] == nums[head + 1] && head < tail) {
                            head++;
                            System.out.println(head);
                        }
                        ;
                        while (nums[tail] == nums[tail - 1] && head < tail) tail--;
                        tail--;
                        head++;
                        //标准答案
                        for (head++; head < tail && nums[head] == nums[head - 1]; head++)
                            System.out.println(head); // 跳过重复数字
                        for (tail--; tail > head && nums[tail] == nums[tail + 1]; tail--) ; // 跳过重复数字

                    }
                }
            }
        }
        return quadruplets;
    }

    public List<List<Integer>> fourSum1(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            long x = nums[i];
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (x + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
            for (int j = i; j < n - 2; j++) {
                long y = nums[j];
                if (j > i+1 && nums[j] == nums[j - 1]) continue;
                if (x + y + nums[j + 1] + nums[j + 2] > target) break;
                if (x + y + nums[n - 1] + nums[n - 2] < target) continue;
                int head = j + 1, tail = n - 1;
                while (head < tail) {
                    long sum = x + y + nums[head] + nums[tail];
                    if (sum > target) tail--;
                    else if (sum < target) head++;
                    else {
                        List<Integer> list = Arrays.asList((int) x, (int) y, nums[head], nums[tail]);
                        ans.add(list);
                        head = head + 1;
                        tail = tail - 1;
                        while (nums[head] == nums[head - 1] && head < tail) head++;
                        while (nums[tail] == nums[tail + 1] && head < tail) tail--;
//                        for (head++; head < tail && nums[head] == nums[head - 1]; head++) ;
//                        for (tail--; head < tail && nums[tail] == nums[tail + 1]; tail--) ;
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Problem18 problem18 = new Problem18();
        int[] nums = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> lists = problem18.fourSum1(nums, 0);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }

    }

}
